Garbage collection, also commonly referred to as automatic memory management, attempts to automatically recycle dynamically allocated memory. Dynamically allocated memory is memory that is created at runtime and that is stored in an area of memory commonly referred to as the heap. There are several techniques that have been developed to perform garbage collection.
One technique is full garbage collection. During full garbage collection, the entire heap is analyzed to determine which memory to recycle. A disadvantage with this technique is that as the heap becomes larger and larger, garbage collection causes a significant delay to programs that are executing. This delay prohibits utilizing full garbage collection when the heap becomes too large.
Another type of garbage collection, commonly referred to as an incremental, generational, or ephemeral garbage collection, attempts to overcome this execution delay by dividing the heap into two or more generations. Newly created objects are allocated in the “youngest” generation. Ephemeral garbage collection then analyzes the “youngest” generation frequently in order to collect and recycle these objects. The older generations are analyzed less frequently, and, when recycled, all of the objects in the older generation are recycled together. Objects in the “youngest” generation that survive a certain number of collections may be “promoted” to the next older generation. Because the ephemeral garbage collection is typically performed on a small portion of the entire heap, ephemeral garbage collection does not impact the execution of programs in a significant manner.
However, even though ephemeral garbage collection does not directly impact the execution of programs in a significant manner, it does cause other problems. One problem occurs when older generations contain pointers that reference younger generations. Without scanning all the older generations, objects in the younger generation may be erroneously recycled. However, if all the generations are scanned, then the benefits of having multiple generations disappear. Fortunately, techniques have been developed to overcome this problem.
One technique, commonly referred to as card marking, divides the heap into cards of equal size. The size of the card may vary, but it is typically bigger than a word and smaller than a page. There are various acceptable methods of marking objects. For example, a single bit within a card bitmap can be changed to indicate when the memory associated with the card has been “touched” or accessed (e.g., written to). Thus, when performing ephemeral garbage collection, the objects in the youngest generation and the objects in each of the cards in the older generations that are indicated as being written into are analyzed. The term “written card” is used through-out this document to refer to a card that contains memory locations that have been “touched”. While card marking greatly reduces the amount of heap that is analyzed during garbage collection, the efficiency of card marking is dependent on the size of the heap. For example, if the card size becomes too large, the cost of analyzing each of the objects in each of the marked cards becomes prohibitive. On the other hand, if the card size is too small and there are numerous cards, the overhead of having so many cards becomes prohibitive. Thus, the benefit of ephemeral garbage collection employing card marking also decreases as the size of the heap increases.
Recently, a new technique has emerged that helps minimize the dependency of ephemeral garbage collection on the heap size. This new technique implements a hierarchy of bundles where each bundle is associated with multiple cards. A bundle bit map is employed where each bit represents one of the bundles. During garbage collection, the bundle bit map is checked to determine which bundles have objects that have been accessed. If the bundle bit map indicates that an object within the bundle has been accessed, each card in that bundle is checked to see if it has been accessed. If it has, then each of its objects is checked. While this technique improves the efficiency of the ephemeral garbage collection, the cost of executing the program is doubled. For example, turning to FIG. 1, pseudo-code 100 illustrating a portion of helper code 102 called by a compiler is shown. The helper code 102 is called whenever a store operation (e.g., “=” operator) is encountered in the program that is being executed. A first statement 104 performs the necessary work of storing a value into the location specified in the program. The second statement 106 performs overhead for marking the card associated with the location, assuming the location is not in the “youngest” generation. The third statement 108 performs overhead for marking the bundle associated with the location. Therefore, the addition of statement 106 to perform bundling doubles the overhead for executing the store operator 104 in comparison to only performing card-marking (statement 106). Because programs typically contains several store operations, which are commonly within a loop, this doubling of execution for each store operation becomes unacceptable and implementing bundles becomes prohibitive.
Thus, until now, there has not been a satisfactory solution for ephemeral garbage collection of a large heap.